package com.zhugang.week03;

import java.util.Stack;

/**
 * @program algorithms
 * @description: calculateBase
 * @author: chanzhugang
 * @create: 2022/06/05 15:42
 */
public class StackCalculateBase {

    public static void main(String[] args) {
        StackCalculateBase base = new StackCalculateBase();
        String s = "2*(5+5*2)/3+(6/2+8)";
        int res = base.calculate(s);
        System.out.println(res);
    }

    /**
     * 772. 基本计算器III（多了括号）
     *
     * @param s
     * @return
     */
    public int calculate(String s) {
        /**
         * 1、数字直接入栈
         * 2、运算符：
         *  a、栈空或者 c > 栈顶运算符， c入栈
         *  b、c < 栈顶运算符，出栈计算
         * 3、如果是'(',直接入栈
         * 4、如是')'，出栈计算，直至碰到'('为止
         */
        Stack<Integer> nums = new Stack<>();
        Stack<Character> ops = new Stack<>();
        int i = 0;
        int n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == ' ') {
                i++;
            } else if (isDigit(c)) {
                int number = 0;
                while (i < n && isDigit(s.charAt(i))) {
                    // 连续字符转数字
                    number = number * 10 + (s.charAt(i) - '0');
                    i++;
                }
                nums.push(number);
            } else if (c == '(') {
                ops.push(c);
                i++;
            } else if (c == ')') {
                while (!ops.isEmpty() && ops.peek() != '(') {
                    fetchAndCal(nums, ops);
                }
                // 弹出'（'
                ops.pop();
                i++;
            } else {
                while (!ops.isEmpty() && !prior(c, ops.peek())) {
                    // 出栈计算
                    fetchAndCal(nums, ops);
                }
                ops.push(c);
                i++;
               /* if (ops.isEmpty() || prior(c, ops.peek())) {
                    ops.push(c);
                } else {
                    while (!ops.isEmpty() && !prior(c, ops.peek())) {
                        // 出栈计算
                        fetchAndCal(nums, ops);
                    }
                    ops.push(c);
                }
                i++;*/
            }
        }
        while (!ops.isEmpty()) {
            fetchAndCal(nums, ops);
        }
        return nums.pop();
    }

    private void fetchAndCal(Stack<Integer> nums, Stack<Character> ops) {
        Integer num2 = nums.pop();
        Integer num1 = nums.pop();
        char op = ops.pop();
        int res = cal(op, num1, num2);
        // 计算结果压入数字栈
        nums.push(res);
    }

    private int cal(char op, Integer num1, Integer num2) {
        switch (op) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
        }
        return -1;
    }

    private boolean prior(char a, char b) {
        if ((a == '*' || a == '/') && (b == '+' || b == '-')) {
            return true;
        }
        // 此处优先级也高
        return b == '(';
    }

    private boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }
}